﻿#include <iostream>
#include "BinaryTree.h"

#define MAX(a,b) (a>b?a:b)

static int process(BinaryTreeNode* head, int prevSum)
{
    if (!head) return prevSum;

    // 使用当前节点的值
    int useCurLeft = process(head->left, head->getValue() + prevSum);
    int useCurRight = process(head->right, head->getValue() + prevSum);

    // 从当前节点开始
    int startWithCurLeft = process(head->left, head->getValue());
    int startWithCurRight = process(head->right, head->getValue());

    // 不从当前节点开始
    int startWithoutCurLeft = process(head->left, 0);
    int startWithoutCurRight = process(head->right, 0);

    // 当前节点结束
    int overCur = prevSum + head->getValue();

	
    int a = MAX(startWithCurLeft, startWithoutCurLeft);
    int b = MAX(startWithCurRight, startWithoutCurRight);
    int c = MAX(useCurLeft, useCurRight);

    int d = MAX(a, b);
    int e = MAX(c, d);
    int f = MAX(e, overCur);
    return f;
}

/**
 * 给定一颗二叉树的头节点head，可以从树中的任一点出发，如果走的话只能向下走，也可以选择随时停止，所形成的轨迹叫做一条路径，路径上所有值的累加和叫做路径和。求这棵树上的最大路径和.
 */
int main_maximumOfPaths()
{
    auto head = new BinaryTreeNode(1, -2);
    head->left = new BinaryTreeNode(2, 2);
    head->right = new BinaryTreeNode(3, 4);
    head->left->left = new BinaryTreeNode(4, 1);
    head->left->right = new BinaryTreeNode(5, 2);
    head->right->left = new BinaryTreeNode(6, -30);
    head->right->right = new BinaryTreeNode(7, 0);
    head->left->left->left = new BinaryTreeNode(8, 3);
    head->left->right->right = new BinaryTreeNode(11, 9);
    head->right->left->left = new BinaryTreeNode(12, 15);
    head->right->left->right = new BinaryTreeNode(13, 1);
    head->right->right->right = new BinaryTreeNode(15, 8);

    auto maxPathLen = process(head, 0);
    printf("%d\n", maxPathLen);

    return 0;
}